This invention relates to the field of modeling interactions, specifically modeling interactions among complex polyhedra in motion.
Many robotics applications require modeling of interactions. For example, collision detection is a basic problem in robotics and related areas, arising in motion planning, control, graphical programming, motion-preview, virtual reality, and dynamical simulation. The collision detection problem asks whether a rigid body moving along a given path intersects with any of a set of obstacles at any point on that path. In a fuller version of the problem, all contacts must also be determined. In both cases, accuracy is of extreme importance when the results of collision detection between modeled objects affect the behavior of physical robots or influence the outcomes of physical simulations, such as those used in process and product design and evaluation.
Most current methods for collision detection rely on interference detection or distance computation. A few recent algorithms are very fast, using queries at steps in the bodies' motion. However, the difficulty of determining collisions or distances between steps mandates the use of very small step sizes, consequently reducing efficiency.
Interference detection (or collision detection) for a rigid body R at a position and orientation x and obstacles O means to determine whether R(x).andgate.O is non-empty, with R(x) denoting the image of R in the world. Distance computation means to determine the minimum distance between all points in R(x) and those in O. Simple collision detection for a rigid body R moving over a path segment among obstacles O means to determine whether at any point along the path the body contacts or intersects any obstacles. In other words, if we let C denote the space of positions and orientations and let p: [0,1].fwdarw.C denote the path segment, then collision detection asks whether there is any t.di-elect cons.[0,1] such that R(p(t)).andgate.O is non-empty.
Exact or accurate collision detection is often avoided for the sake of speed. Usually, either interference detection or distance computation queries are applied at closely spaced points on the path. Simple use of interference detection can miss collisions. Growing the objects by a safety margin can prevent this, but at the risk of detecting false collisions. With distance computation, one can vary the step size to reduce the number of queries needed to obtain a given resolution, but resolution is limited by the minimum step size.
For a number of years, hierarchical geometric representations have been used to avoid "all pairs" comparisons in interference detection, distance computation, and collision detection. The binary-space partitioning tree (BSPtree) and variants have been successfully used in exact interference checking and contact determination, but they do not readily yield distance information. See, e.g., Fuchs et al., "On visible surface generation by a priori tree structures," Proc. of ACM SIGGRAPH, pages 124-133,1980. The octree is another space-partitioning data-structure that has been used in interference detection, but it must be used with other geometric objects to obtain computations matching the accuracy of faceted boundary representations or BSP-trees. See, e.g., Jackins et al., "Octrees and their use in representing three-dimensional objects," Computer Graphics and Image Processing, (14):249-270, 1980; Meagher, "Geometric modeling using octree encoding," Computer Graphics and Image Processing, (19): 129-147, 1982.
Other hierarchical structures use various primitives to bound an object or its surface at each level of the hierarchy, although sometimes holes are treated explicitly. See, e.g., Faverion, "Hierarchical object models for efficient anti-collision algorithms," Proc. IEEE ICRA 1989, pages 333-340, Scottsdale, Ariz., 1989. Successful implementations for exact interference detection and distance computation have been based on several geometric primitives. Convex-hull based implementations, sphere-based techniques, and bounding-prism methods are among those known to be fast. See, e.g., Cameron, "Dealing with geometric complexity in motion planning," IEEE ICRA 1996 Workshop on Practical Motion Planning in Robotics," Minneapolis, Min., 1996; Quinlan, "Efficient distance computation between non-convex objects," Proc. 1994 IEEE Int'l Conf on Robotics and Automation, San Diego, Calif., 1994; Sato et al., "Efficient collision detection using fast distance calculation algorithms for convex and non-convex objects," Proc. 1995 IEEE Int'l Conf on Robodcs and Automation, pages 772-778, Minneapolis, Min., April 1996; Gottschalk et al., "OBB-tree: A hierarchical structure for rapid interference detection," Proc ACM SIGGRAPH'90, 1996. However, none of these results cover swept-body distance or swept-body interference detection.
Canny described a technique for exact collision detection for convex polyhedra moving along path segments linear in translation and the quaternion representation of SO(3). See Canny, "Collision detection for moving polyhedra," IEEE Trans. on Pattern Analysis and Machine Intelligence, 8(2):200-209, 1986. Finally, Cameron used space-time techniques and develops algorithms and hierarchical structures for exact collision detection for non-convex objects. See Cameron, "Collision detection by 4D intersection testing," Int'l Journal of Robotics Research, 6(3):291-302, June 1990. Both these results are general in allowing exact time intervals of contact and penetration to be computed directly. Canny, however, only computes interactions between convex objects. Cameron describes a theoretical method for objects modeled by Boolean constructive solid geometry (CSG) trees and an implemented method of objects modeled by Boolean CSG trees with linear half-spaces at their leaves. The implemented method of Cameron is complicated and might be computationally expensive for a large class of non-convex objects, particularly those whose CSG models include difference operator. Neither Canny nor Cameron provides computation of the minimal clearance distance between bodies that do not collide.
Current technology thus provides two options, even when the motions are linear translations: (i) distance computation or interference detection between moving objects at discrete points in time; and (ii) exact collision detection in space-time without clearance distances that has limitations with regard to non-convex objects. The first option often requires very small motion steps for robustness (e.g., to not miss collisions), which causes a performance penalty in simulations, motion planning, graphical programming, and motion inspection. It is not an option when the motion step-size cannot be arbitrarily controlled, which is the case with currently available virtual reality motion-capture systems. Because many objects in the world are non-convex, the second option is of limited use in the applications mentioned above. Furthermore, the lack of robust minimal clearance distance computation during motion limits what is feasible in safety analyses.
There is therefore a need for a method and apparatus for modeling interactions between moving bodies that is faster and more robust than current approaches.